#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define MAX_SIZE 100

typedef struct {
    double items[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, double value) {
    if (s->top < MAX_SIZE - 1) {
        s->items[++s->top] = value;
    } else {
        printf("Stack Full\n");
    }
}

double pop(Stack *s) {
    if (s->top >= 0) {
        return s->items[s->top--];
    } else {
        printf("Stack Empty\n");
        return -1;
    }
}

int isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

int precedence(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

int infixToPostfix(char *infix, char *postfix) {
    Stack s;
    s.top = -1;
    int i, j = 0;

    for (i = 0; infix[i]; i++) {
        if (isdigit(infix[i]) || infix[i] == '.') {
            postfix[j++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (s.top != -1 && s.items[s.top] != '(') {
                postfix[j++] = ' ';
                postfix[j++] = pop(&s);
            }
            if (s.top == -1) {
                printf("mismatched parenthesis\n");
                return -1;
            }
            pop(&s);  // Pop the '('
        } else if (isOperator(infix[i])) {
            postfix[j++] = ' ';
            while (s.top != -1 && precedence(s.items[s.top]) >= precedence(infix[i])) {
                postfix[j++] = pop(&s);
                postfix[j++] = ' ';
            }
            push(&s, infix[i]);
        } else {
            printf("invalid character %c\n", infix[i]);
            return -1;
        }
    }

    while (s.top != -1) {
        postfix[j++] = ' ';
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0';

    return 0;
}

double evaluatePostfix(char *postfix) {
    Stack s;
    s.top = -1;
    double a, b;
    char *token = strtok(postfix, " ");

    while (token != NULL) {
        if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
            push(&s, atof(token));
        } else {
            b = pop(&s);
            a = pop(&s);
            switch (token[0]) {
                case '+':
                    push(&s, a + b);
                    break;
                case '-':
                    push(&s, a - b);
                    break;
                case '*':
                    push(&s, a * b);
                    break;
                case '/':
                    push(&s, a / b);
                    break;
            }
        }
        token = strtok(NULL, " ");
    }
    return pop(&s);
}

int main() {
    int ret = -1;
    char infix[100], postfix[100];
    printf("Enter an infix expression: ");
    scanf("%s", infix);
    ret = infixToPostfix(infix, postfix);
    if (ret < 0) {
        return -1;
    }
    printf("Postfix expression: %s\n", postfix);
    printf("Result: %lf\n", evaluatePostfix(postfix));

    return 0;
}
